2022-11-22-Dijkstra最短路算法

算法过程

假设我们用数据结构维护每个点的

初始化并加入 , 其余点的设为无限大, 所有点标记为未访问
重复3-5，直到没有未访问的点，算法结束
从中选出最小且未访问的点，记为（中查询）
把标记为已访问并把它从中删除（中删除）
对所有出边进行松弛操作（中修改和插入）

适用范围

单源多汇最短路，无负权边

解释

已经访问的点是已经确定了最短路的点，未访问的点是有待确认的点

对于一个未访问的点中最小的点，它的首先已经被已经访问过的点松弛过了，所以能让它更小的未访问的点不存在

而其他的点的都不比它小，且边权非负，也不能让更小，所以这个点的最短路确定就是了

对不同的复杂度分析

暴力

操作3的总复杂度为

操作5的总复杂度为

复杂度

堆

操作3总复杂度为

操作4总复杂度为

操作5总复杂度为

复杂度

优先队列

类似于堆，但是没有修改和删除操作，所以队内元素有个

操作3总复杂度为

操作5总复杂度为

复杂度

不过，因为最多是的

结论

稀疏图中，，优先队列复杂度比暴力更优

稠密图中，，暴力复杂度反而更优

代码

typedef pair<int, int> pii;

int dis[NV], S;
bool vis[NV];

void Dijkstra() {
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    dis[S] = 0;
    priority_queue<pii, vector<pii>, greater<pii>> q;
    q.push(make_pair(0, S));
    while (!q.empty()) {
        int u = q.top().second;
        q.pop();
        if (vis[u]) continue;
        vis[u] = true;
        for (int i = hd[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            int c = e[i].c;
            if (dis[v] > dis[u] + c) {
                dis[v] = dis[u] + c;
                q.push(make_pair(dis[v], v));
            }
        }
    }
}

void Dijkstra_BF() {
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, 0, sizeof(vis));
    dis[S] = 0;
    // 每次循环能标记一个点
    for (int iV = 1; iV < n; iV++) {
        int min_dis = INF;
        int u;
        for (int i = 1; i <= n; i++) {
            if (!vis[i] && dis[i] < min_dis) {
                min_dis = dis[i];
                u = i;
            }
        }
        vis[u] = true;
        for (int i = hd[u]; i; i = e[i].nxt) {
            int v = e[i].to;
            int c = e[i].c;
            if (dis[v] > dis[u] + c) {
                dis[v] = dis[u] + c;
            }
        }
    }
}